home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / ingres04.lzh / source / ovqp / strategy.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-09-18  |  9.2 KB  |  331 lines
  1. # include    <ingres.h>
  2. # include    <aux.h>
  3. # include    <catalog.h>
  4. # include    <symbol.h>
  5. # include    <tree.h>
  6. # include    "../decomp/globs.h"
  7. # include    "strategy.h"
  8. # include    <btree.h>
  9. # include    <sccs.h>
  10. # include    <errors.h>
  11.  
  12. SCCSID(@(#)strategy.c    8.4    2/8/85)
  13.  
  14. /*
  15. ** STRATEGY
  16. **
  17. **    Attempts to limit access scan to less than the entire De.ov_source
  18. **    relation by finding a key which can be used for associative
  19. **    access to the De.ov_source reln or an index thereon.  The key is
  20. **    constructed from domain-value specifications found in the
  21. **    clauses of the qualification list using sub-routine findsimp
  22. **    in findsimp.c and other subroutines in file key.c
  23. */
  24.  
  25. strategy()
  26. {
  27.     register int        i, j, allexact;
  28.     struct accessparam    sourceparm, indexparm;
  29.     struct index        itup, rtup;
  30.     struct key        lowikey[MAXKEYS+1], highikey[MAXKEYS+1];
  31.     struct key        lowbkey[MAXKEYS+1], highbkey[MAXKEYS+1];
  32.     register DESC        *d;
  33.     DESC            *openindex();
  34.     extern DESC        Inddes;
  35.     char             *tp;
  36.     long            l_lid[MAXLID], h_lid[MAXLID];
  37.     int            keytype;
  38.     long            last_lid();
  39.     long            page, l, t;
  40.     int            lidsize;
  41.     struct locator        tidloc;
  42.     extern int        Btree_fd;
  43.  
  44. #    ifdef xOTR1
  45.     if (tTf(70, 0))
  46.         printf("STRATEGY\tSource=%.12s\tNewq = %d\n",
  47.                De.ov_source ? De.ov_source->reldum.relid : "(none)",
  48.                De.de_newq);
  49. #    endif
  50.  
  51.     while (De.de_newq)    /* if De.de_newq=TRUE then compute a new strategy */
  52.             /* NOTE: This while loop is executed only once */
  53.     {
  54.         De.ov_scanr = De.ov_source;
  55.     
  56.         if (!De.ov_scanr)
  57.             return (1);    /* return immediately if there is no source relation */
  58.     
  59.         De.ov_fmode = NOKEY;    /* assume a find mode with no key */
  60.     
  61.         if (!De.ov_qlist)
  62.             break;    /* if no qualification then you must scan entire rel */
  63.         /*
  64.         ** Here we check for the special condition
  65.         ** of a where clause consisting only of a tid.
  66.         */
  67.         if (tid_only_test())
  68.             return(1);
  69.  
  70.         /* copy structure of source relation into sourceparm */
  71.         paramd(De.ov_source, &sourceparm);
  72.     
  73.         /* if source is unkeyed and has no sec index then give up */
  74.         if (sourceparm.mode == NOKEY && De.ov_source->reldum.relindxd <= 0 && !De.ov_source->reldum.reldim)
  75.             break;
  76.  
  77.         /* find all simple clauses if any */
  78.         if (!findsimps())
  79.             break;    /* break if there are no simple clauses */
  80.     
  81.         /* Four steps are now performed to try and find a key.
  82.         ** First if the relation is hashed then an exact key is search for
  83.         **
  84.         ** Second if there are secondary indexes, then a search is made
  85.         ** for an exact key. If that fails then a  check is made for
  86.         ** a range key. The result of the rangekey check is saved.
  87.         **
  88.         ** A step to check for possible use of Btrees is made here,
  89.         ** although in actuality, an exact btreekey search is used
  90.         ** after an exact range key search but before a range key search.
  91.         ** A BTree range search is used only as a last alternative
  92.         ** to a no key search.
  93.         **
  94.         ** Third if the relation is an ISAM a check is  made for
  95.         ** an exact key or a range key.
  96.         **
  97.         ** Fourth if there is a secondary index, then if step two
  98.         ** found a key, that key is used.
  99.         **
  100.         **  Lastly, give up and scan the  entire relation
  101.         */
  102.     
  103.         /* step one. Try to find exact key on primary */
  104.         if (exactkey(&sourceparm, De.ov_lkey_struct))
  105.         {
  106.             De.ov_fmode = EXACTKEY;
  107.             break;
  108.         }
  109.     
  110.         /* step two. If there is an index, try to find an exactkey on one of them */
  111.         if (De.ov_source->reldum.relindxd > 0)
  112.         {
  113.     
  114.             opencatalog("indexes", OR_READ);
  115.             setkey(&Inddes, &itup, De.ov_source->reldum.relid, IRELIDP);
  116.             setkey(&Inddes, &itup, De.ov_source->reldum.relowner, IOWNERP);
  117.             if (i = find(&Inddes, EXACTKEY, &De.ov_lotid, &De.ov_hitid, (char *)&itup))
  118.                 syserr("strategy:find indexes %d", i);
  119.     
  120.             while (!(i = get(&Inddes, &De.ov_lotid, &De.ov_hitid, (char *)&itup, NXTTUP)))
  121.             {
  122. #                ifdef xOTR1
  123.                 if (tTf(70, 3))
  124.                     printup(&Inddes, (char *)&itup);
  125. #                endif
  126.                 if (!bequal(itup.irelidp, De.ov_source->reldum.relid, MAXNAME) ||
  127.                     !bequal(itup.iownerp, De.ov_source->reldum.relowner, 2))
  128.                     continue;
  129.                 parami(&itup, &indexparm);
  130.                 if (exactkey(&indexparm, De.ov_lkey_struct))
  131.                 {
  132.                     De.ov_fmode = EXACTKEY;
  133.                     d = openindex(itup.irelidi);
  134.                     /* temp check for 6.0 index */
  135.                     if ((int) d->reldum.relindxd == -1)
  136.                         ov_err(BADSECINDX);
  137.                     De.ov_scanr = d;
  138.                     break;
  139.                 }
  140.                 if (De.ov_fmode == LRANGEKEY)
  141.                     continue;    /* a range key on a s.i. has already been found */
  142.                 if (allexact = rangekey(&indexparm, lowikey, highikey))
  143.                 {
  144.                     bmove((char *)&itup, (char *)&rtup, sizeof itup);    /* save tuple */
  145.                     De.ov_fmode = LRANGEKEY;
  146.                 }
  147.             }
  148.             if (i < 0)
  149.                 syserr("stragery:bad get from index-rel %d", i);
  150.             /* If an exactkey on a secondary index was found, look no more. */
  151.             if (De.ov_fmode == EXACTKEY)
  152.                 break;
  153.         }
  154.     
  155.         /* attempt to use Btree in aiding search */
  156.         if (i = btreekey(lowbkey, highbkey))
  157.         {
  158.             if (i > 0)
  159.                 De.ov_fmode = BTREEKEY; 
  160.             else if (De.ov_fmode != LRANGEKEY)
  161.             /* use range key search over btree range search */
  162.             {
  163.                 keytype = i;
  164.                 De.ov_fmode = BTREERANGE;
  165.             }
  166.         }
  167.  
  168.         /* step three. Look for a range key on primary */
  169.         if (i = rangekey(&sourceparm, De.ov_lkey_struct, De.ov_hkey_struct))
  170.         {
  171.             if (i < 0)
  172.                 De.ov_fmode = EXACTKEY;
  173.             else if (De.ov_fmode == BTREEKEY)
  174.             /* use exact btree search over range search */
  175.             {
  176.                 bmove((char *) lowbkey, (char *) De.ov_lkey_struct, sizeof lowbkey);
  177.                 bmove((char *) highbkey, (char *) De.ov_hkey_struct, sizeof highbkey);
  178.             }
  179.             else
  180.                 De.ov_fmode = LRANGEKEY;
  181.             break;
  182.         }
  183.  
  184.         if (De.ov_fmode == BTREEKEY)
  185.         {
  186.             bmove((char *) lowbkey, (char *) De.ov_lkey_struct, sizeof lowbkey);
  187.             bmove((char *) highbkey, (char *) De.ov_hkey_struct, sizeof highbkey);
  188.             break;
  189.         }
  190.     
  191.         /* last step. If a secondary index range key was found, use it */
  192.         if (De.ov_fmode == LRANGEKEY)
  193.         {
  194.             if (allexact < 0)
  195.                 De.ov_fmode = EXACTKEY;
  196.             d = openindex(rtup.irelidi);
  197.             /* temp check for 6.0 index */
  198.             if ((int) d->reldum.relindxd == -1)
  199.                 ov_err(BADSECINDX);
  200.             De.ov_scanr = d;
  201.             bmove((char *)lowikey, (char *)De.ov_lkey_struct, sizeof lowikey);
  202.             bmove((char *)highikey, (char *)De.ov_hkey_struct, sizeof highikey);
  203.             break;
  204.         }
  205.  
  206.         /* nothing will work. give up! */
  207.         break;
  208.     
  209.     }
  210.  
  211.     /* check for De.de_newq = FALSE and no source relation */
  212.     if (!De.ov_scanr)
  213.         return (1);
  214.     /*
  215.     ** At this point the strategy is determined.
  216.     **
  217.     ** If De.ov_fmode is EXACTKEY then De.ov_lkey_struct contains
  218.     ** the pointers to the keys.
  219.     **
  220.     ** If De.ov_fmode is LRANGEKEY then De.ov_lkey_struct contains
  221.     ** the pointers to the low keys and De.ov_hkey_struct
  222.     ** contains pointers to the high keys.
  223.     **
  224.     ** If De.ov_fmode is BTREEKEY then De.ov_lkey_struct contains
  225.     ** pointers to the key lid.
  226.     **
  227.     ** If De.ov_fmode is BTREERANGE then lowbkey contains pointers
  228.     ** to the low key lid and highbkey contains pointers to the
  229.     ** high key lid.
  230.     **
  231.     ** If De.ov_fmode is NOKEY, then a full scan will be performed
  232.     */
  233. #    ifdef xOTR1
  234.     if (tTf(70, -1))
  235.         printf("De.ov_fmode= %d\n",De.ov_fmode);
  236. #    endif
  237.  
  238.     if (De.ov_fmode == BTREERANGE)
  239.     /* requires special type of search to limit tid scan */
  240.     {
  241.         for (i = 0; i < De.ov_scanr->reldum.reldim; ++i)
  242.         {
  243.             l_lid[i] = 0;
  244.             h_lid[i] = 0;
  245.         }
  246.         lidsize = LIDSIZE * De.ov_scanr->reldum.reldim;
  247.         /* get low lids */
  248.         if (keytype == -1 || keytype == -3)
  249.         {
  250.             tp = De.ov_keyl + De.ov_scanr->reldum.relwid - lidsize;
  251.             bmove(l_lid, tp, lidsize);
  252.             setallkey(lowbkey, De.ov_keyl);
  253.             bmove(tp, l_lid, lidsize);
  254.         }
  255.         /* get high lids */
  256.         if (keytype == -2 || keytype == -3)
  257.         {
  258.             tp = De.ov_keyh + De.ov_scanr->reldum.relwid - lidsize;
  259.             bmove(h_lid, tp, lidsize);
  260.             setallkey(highbkey, De.ov_keyh);
  261.             bmove(tp, h_lid, lidsize);
  262.         }
  263.         Btree_fd = De.ov_scanr->btree_fd;
  264.         /* scan through lids to fill in unprovided lids and to check
  265.         ** for lids that are too big
  266.         */
  267.         page = RT;
  268.         for (i = 0; i < De.ov_scanr->reldum.reldim; ++i)
  269.         {
  270.             if (l_lid[i] <= 0) 
  271.                 l_lid[i] = 1;
  272.             l = last_lid(page) - 1;
  273.             if (*h_lid < 0)
  274.                 return(0);
  275.             if (!h_lid[i] || h_lid[i] > l)
  276.                 h_lid[i] = l;
  277.             if ((t = get_tid(page, h_lid[i], &tidloc)) < 0)
  278.                 syserr("bad gettid in strategy, lid = %ld\n", h_lid[i]);
  279.             page = t;
  280.         }
  281.         /* check whether lo > hi */
  282.         for (i = 0; i < De.ov_scanr->reldum.reldim; ++i)
  283.             if (l_lid[i] < h_lid[i])
  284.                 break;
  285.             else if (l_lid[i] > h_lid[i])
  286.                 return(0);
  287. #        ifdef xOTR1
  288.         if (tTf(70,0))
  289.             for (i = 0 ; i < De.ov_scanr->reldum.reldim; ++i)
  290.                 printf("hi = %ld, lo = %ld\n", h_lid[i], l_lid[i]);
  291. #        endif
  292.         /* find the smallest and largest possible tids of the lids
  293.         ** within the provided range */
  294.         btreerange(De.ov_scanr, l_lid, h_lid, &De.ov_lotid, &De.ov_hitid);
  295.     }
  296.     else
  297.     {
  298.         /* set up the key tuples */
  299.         if (De.ov_fmode != NOKEY)
  300.         {
  301.             if (setallkey(De.ov_lkey_struct, De.ov_keyl))
  302.                 return (0);    /* query false. There is a simple
  303.                         ** clause which can never be satisfied.
  304.                         ** These simple clauses can be choosey!
  305.                         */
  306.         }
  307.     
  308.         if (i = find(De.ov_scanr, De.ov_fmode, &De.ov_lotid, &De.ov_hitid, De.ov_keyl))
  309.             syserr("strategy:find1 %.12s, %d", De.ov_scanr->reldum.relid, i);
  310.  
  311.         if (De.ov_fmode == LRANGEKEY)
  312.         {
  313.             setallkey(De.ov_hkey_struct, De.ov_keyh);
  314.         if (i = find(De.ov_scanr, HRANGEKEY, &De.ov_lotid, &De.ov_hitid, De.ov_keyh))
  315.                 syserr("strategy:find2 %.12s, %d", De.ov_scanr->reldum.relid, i);
  316.         }
  317.     }
  318.     
  319. #    ifdef xOTR1
  320.     if (tTf(70, 1))
  321.     {
  322.         printf("Lo");
  323.         dumptid(&De.ov_lotid);
  324.         printf("Hi");
  325.         dumptid(&De.ov_hitid);
  326.     }
  327. #    endif
  328.  
  329.     return (1);
  330. }
  331.